package solution.liuyu2783.offer;

/**
 * 剑指 Offer 10- I. 斐波那契数列
 *
 */
public class Q10_Fibonacci_E {

	/**
	 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下
	 * F(0) = 0,   F(1) = 1
	   F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
	 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
	 */
	public static void main(String[] args) {
		int result = Q10_Fibonacci_E.fibDp(48);
		System.out.print("result= "+ result);
	}
	
	/**
	 * 递归
	 * @param i
	 * @return
	 */
	public static int fib(int i) {
		if(i == 0) {
			return 0;
		}
		else if(i == 1) {
			return 1;
		}
		return fib(i -1) + fib(i -2);
	}
	
	/**
	 * 动态规划
	 * @param n
	 * @return
	 */
	public static int fibDp(int n) {
		int[] dp = new int[n +1];
		dp[0] =0;
		dp[1] = 1;
		for(int i = 2; i <= n ; i++) {
			dp[i] = dp[i-1] + dp[i -2];
			dp[i] %= 1000000007;
		}
		return dp[n];
	}
}
